#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>ku;
int  support;
int line=0;
int sum=0;
int a[20000]={0};
string ak;
typedef struct Node*node;
struct Node
{
    int key=-1;
    int vl=0;
    int truelist=0;
    node father=NULL;
    vector<node>child;
};
struct treelist{
    int key;
    int v;
    vector<node>next;
};
vector<vector<int>>newku;
bool cmp(treelist a,treelist b)
{   if(a.v!=b.v)
        return a.v>b.v;
    else
        return a.key>b.key;
}
void duxie()
{

    ifstream ifs;
    ifs.open("retail.txt",ios::in);

    if (!ifs.is_open())
    {
        cout<<"fail";

    }
    while (getline(ifs,ak)) {
        stringstream ss;
        ss << ak;
        string temp;
        vector<int>temp1;
        while (ss>>temp)
            temp1.push_back(stoi(temp));
        ku.push_back(temp1);
    }
    ifs.close();

}
bool nocuttree(node treeexample)
{
    int flag=1;
    while (treeexample)
    {
        if(treeexample->child.size()>1) {
            flag = 0;
            break;
        } else if (treeexample->child.size()==0)
        {
            break;
        }
        else
        {treeexample=treeexample->child[0];}

    }

    if(flag==1)
        return true;
    else
        return false;
}
vector<vector<int>>builtku(treelist head)
{

    vector<vector<int>> temp;
    for (int i = 0; i <head.next.size() ; ++i) {
        vector<int> temp1;
        node ndtemp=head.next[i];
        int number=ndtemp->vl;
        ndtemp=ndtemp->father;
        while (ndtemp->key!=-1)
        {
            temp1.push_back(ndtemp->key);
            ndtemp=ndtemp->father;
        }
        reverse(temp1.begin(),temp1.end());
        for (int j = 0; j <number ; ++j) {
            temp.push_back(temp1);
        }

    }

    return temp;
}
vector<vector<int>>cutoften2(vector<vector<int>> tempku,vector<treelist>&tlist1)
{
    int a[20000]={0};
    int supportkusize=support;

    for (int i = 0; i < tempku.size(); ++i) {
        for (int j = 0; j < tempku[i].size(); ++j) {
            a[tempku[i][j]]++;
        }
    }
    for (int i = 0; i < 20000; ++i) {
        if(a[i]>=supportkusize)
            tlist1.push_back({i,a[i]});
    }
    sort(tlist1.begin(),tlist1.end(),cmp);
    vector<vector<int>>temp;

    for (int i = 0; i < tempku.size(); ++i) {
        vector<int>temp1;
        for (int j = 0; j < tempku[i].size(); ++j) {
            if(a[tempku[i][j]]>=supportkusize)
                temp1.push_back(tempku[i][j]);
        }
        if(temp1.size()!=0)
            temp.push_back(temp1);
    }

    return temp;

}
node builttree2(vector<vector<int>>kut,vector<treelist>&tlist)
{

    node treehead=new Node;
    node treeheadcun=treehead;
    for (int i = 0; i < kut.size(); ++i) {
        for (int j = 0; j < kut[i].size(); ++j) {
            node temp=new Node;
            temp->key=kut[i][j];
            temp->vl++;

            if(j==0&&i==0)
            {
                treehead->child.push_back(temp);
                temp->father=treehead;
                treehead=treehead->child[0];
                for (int k = 0; k < tlist.size(); ++k) {
                    if(temp->key==tlist[k].key)
                        tlist[k].next.push_back(temp);
                }

            }
            else if(j==0)
            {
                int index=-1;
                for (int k = 0; k < treehead->child.size(); ++k) {
                    if(treehead->child[k]->key==kut[i][j])
                    {
                        index=k;
                    }
                }
                if (index!=-1)
                {
                    treehead=treehead->child[index];
                    treehead->vl++;

                } else
                {
                    treehead->child.push_back(temp);
                    temp->father=treehead;
                    treehead=temp;
                    for (int k = 0; k < tlist.size(); ++k) {
                        if(temp->key==tlist[k].key)
                            tlist[k].next.push_back(temp);
                    }
                }
            } else {

                int index = -1;
                for (int k = 0; k < treehead->child.size(); ++k) {
                    if (treehead->child[k]->key == kut[i][j]) {
                        index = k;
                    }
                }
                if (index != -1) {
                    treehead = treehead->child[index];
                    treehead->vl++;

                } else {
                    treehead->child.push_back(temp);
                    treehead->child[(treehead->child.size()-1)]->father=treehead;
                    treehead=treehead->child[(treehead->child.size()-1)];
                    for (int k = 0; k < tlist.size(); ++k) {
                        if(temp->key==tlist[k].key)
                            tlist[k].next.push_back(temp);
                    }
                }


            }



        }

        treehead=treeheadcun;

    }

    return treeheadcun;

}
vector<int>zuhe1(node treehead)
{
    vector<int>temp;
    if(treehead->child.size()==0)
    {
        vector<int>temp2;
        return temp2;
    } else
        treehead=treehead->child[0];

    while (treehead->child.size()>0)
    {
        temp.push_back(treehead->key);
        treehead=treehead->child[0];
    }
    temp.push_back(treehead->key);

    return temp;
}
int xiangjishu[1000]={0};
int C(int n,int m){
    if(m==0 || m == n) return 1;
    return C(n-1,m)+C(n-1,m-1);
}

void  solvetree(node treehead,vector<treelist>tlist,vector<int>qianzhui,vector<int>zuhe)
{

    if (nocuttree(treehead))
    {

        vector<int> temp1;
        temp1=zuhe1(treehead);
        if(temp1.size()!=0)
        {
            for (int i = 1; i <=temp1.size() ; ++i) {
                xiangjishu[qianzhui.size()+i]+= C(temp1.size(),i);
            }
        }
        return;


    }

    for (int i = tlist.size()-1; i>=0; i--) {
        vector<treelist>temptlist;

        vector<vector<int>> tempku=cutoften2( builtku(tlist[i]), temptlist);

        node temptree=builttree2(tempku,temptlist);
        qianzhui.push_back(tlist[i].key);
        xiangjishu[qianzhui.size()]++;
        solvetree(temptree,temptlist,qianzhui,zuhe);
        qianzhui.erase(qianzhui.end());
    }
}
int main()
{
    auto start_time = std::chrono::steady_clock::now();
    duxie();
    vector<int>jilu;
    vector<vector<int>>sure,prolib,temp;
    for (int i = 0; i < ku.size(); ++i) {
        for (int j = 0; j < ku[i].size(); ++j) {
            a[ku[i][j]]++;

        }
    }
    support= ceil(ku.size()*0.01);
    vector<treelist>tlist;
    vector<vector<int>>temp11= cutoften2(ku,tlist);
    node teep=builttree2(temp11,tlist);
    vector<int>qianzhui;
    vector<int>zuhe;

    solvetree(teep,tlist,qianzhui,zuhe);
    auto end_time = std::chrono::steady_clock::now();
    auto elapsed_time = end_time - start_time;
    int num=0;

    // 输出时间间隔
    std::cout << "Elapsed time: " << std::chrono::duration<double>(elapsed_time).count() << " seconds\n";
    for (int i = 1; xiangjishu[i]!=0; ++i) {
        cout<<xiangjishu[i]<<" ";
        num+=xiangjishu[i];
    }
    cout<<endl;
    cout<<num;
}
